#include<stdio.h>
#include<stdlib.h>
#include"LinkTree.h"
#define true 1
#define false 0

TNode *CreateTreeNode(ElementType element)
{
    TNode *treeNode=(TNode *)malloc(sizeof(TNode));
    if(treeNode==NULL)
    {
        printf("treeNode malloc error!\n");
        return NULL;
    }
    treeNode->data=element;
    treeNode->parent=NULL;
    treeNode->firstChild=NULL;
    treeNode->nextSbiling=NULL;
    return treeNode;
}

void ConnectBranch(TNode *parent, TNode *child)
{
    if(parent==NULL || child==NULL)
    {
        return;
    }
    child->nextSbiling=parent->firstChild;
    parent->firstChild=child;
    child->parent=parent;
}

void DisconnectBranch(TNode *parent, TNode *child)
{
    if(parent==NULL || child==NULL || parent->firstChild==NULL)
    {
        return;
    }   

    TNode *TravelPoint=parent->firstChild;
    if(parent->firstChild==child)
    {
        parent->firstChild=TravelPoint->nextSbiling;
        child->parent=NULL;
        child->nextSbiling=NULL;       
        return;
    }
    while(TravelPoint->nextSbiling!=NULL)
    {
        if(TravelPoint->nextSbiling==child)
        {
            TravelPoint->nextSbiling=TravelPoint->nextSbiling->nextSbiling;
            child->parent=NULL;
            child->nextSbiling=NULL;
            break;
        }
        TravelPoint=TravelPoint->nextSbiling;
    }
}

void FreeNode(TNode *node)
{
    if(node==NULL)
        return;
    TNode *TravelPoint=node->firstChild;
    while(TravelPoint!=NULL)
    {
        TNode *next=TravelPoint->nextSbiling;
        FreeNode(TravelPoint);
        TravelPoint=next;
    }
    free(node);
}

int GetTreeHeight(TNode *node)
{
    if(node==NULL)
        return 0;
    else
    {
        int height=0;
        TNode *childPoint=node->firstChild;
        while(childPoint!=NULL)
        {
            int childHeight=GetTreeHeight(childPoint);
            height=height>childHeight ? height :childHeight;
            childPoint=childPoint->nextSbiling;  
        }
        return height+1;
    }
    return 0;
}

int GetChildCount(TNode *node)
{
    if(node==NULL)
        return 0;
    TNode *childPoint=node->firstChild;
    int count=0;
    while(childPoint!=NULL)
    {
        count++;
        childPoint=childPoint->nextSbiling;
    }
    return count;
}

TNode *FindNode(TNode *node,ElementType data, int (*p)(ElementType,ElementType))
{
    if(node==NULL)
        return NULL;
    if(p(node->data,data) && node->parent!=NULL) 
    {
        return node;
    }
    TNode *childPoint=node->firstChild;
    TNode *targetNode =NULL;
    while(childPoint!=NULL)
    {
        targetNode=FindNode(childPoint,data,p);
        if(targetNode!=NULL)
        {
            return targetNode;
        }
        childPoint=childPoint->nextSbiling;
    }   
    return targetNode;
}

TNode *CopyTree(TNode *node)
{
    if(node==NULL)
        return NULL;
    TNode *newNode=CreateTreeNode(node->data);
    TNode *childNode=node->firstChild;
    while(childNode!=NULL)
    {
        TNode *newChildNode=CopyTree(childNode);
        ConnectBranch(newNode,newChildNode);
        childNode=childNode->nextSbiling;
    }
    return newNode;
}

int InitTree(LTree *tree)
{
    tree->root=CreateTreeNode("");
    if(tree->root==NULL)
    {
        return false;
    }
    else
    {
        return true;
    }
    return 0;
}

void PrintTreeNode(TNode *node,int deepth)
{
    if(node==NULL)
        return;
    if(node->parent!=NULL)
    {
        for(int i=0;i<deepth-1;i++)
            printf("   |_");
        printf("%s\n",node->data);
    }
    struct TreeNode *child=node->firstChild;
    while(child!=NULL)
    {
        PrintTreeNode(child,deepth+1);
        child=child->nextSbiling;
    }
}

void Travel(LTree *tree)
{
    PrintTreeNode(tree->root,0);
}

void FreeTree(LTree *tree)
{
    FreeNode(tree->root);
    tree->root=NULL;
}
